Conventional high-speed communications on copper media (e.g. standard telephone lines) and the like utilize DMT technology and are bundled under the umbrella of xDSL. Several variants of this technology are currently deployed, namely asymmetric digital subscriber line (ADSL), asymmetric digital subscriber line 2 (ADSL2), asymmetric digital subscriber line 2 plus (ADSL2plus), and very high-speed digital subscriber line (VDSL). Some of these technologies are standardized by the International Telecommunications Union (ITU), Geneva, as follows: “ITU-T Recommendation G992.1, Asymmetric Digital Subscriber Line (ADSL),” “ITU-T Recommendation G992.3, Asymmetric Digital Subscriber Line Transceivers 2 (ADSL2),” “ITU-T Recommendation G992.5, Asymmetric Digital Subscriber Line (ADSL) Transceivers—Extended Bandwidth ADSL2 (ADSL2plus),” and “ITU-T Recommendation G993.1, Very High-Speed Asymmetric Digital Subscriber Line (VDSL) Transceivers.” Future technologies are the subject of ongoing standardization efforts.
One key feature of such xDSL systems is the use of FEC to combat the effects of impulse noise and the like. To enhance the effectiveness of FEC, a convolutional interleaver is utilized to spread error patterns over a plurality of DMT symbols, thus allowing for the correction of errors without introducing excessive redundancy, and hence overhead. The convolutional interleaver is defined by the following relationship:Δj=(D−1)j, j=1, . . . , I−1,where Δj is the distance between two interleaved bytes, D is the interleaver depth in bytes, and I is the interleaver block size in bytes.
A necessary condition of such a convolutional interleaver is that D and I must be co-prime (i.e. have no common divisor). This is enforced in several different ways:in ADSL D=2n, I=N=odd integer, andin VDSL D=M·I+1, with N=q·I, where q is an integer. A generalized form of the above VDSL convolutional interleaver has also been considered where:in any DSL D=M·I+x, with N=q·I, x=1, . . . , I−1,with the constraint that x is chosen such that D and I are co-prime.
The VDSL form of the convolutional interleaver wherein:D=M·I+1, with N=q·I has been referred to as “triangular” due to an implementation known to those of ordinary skill in the art utilizing shift registers of varying sizes in a triangular pattern. Such a convolutional interleaver needs only (D−1)*(I−1)/2 memory locations. However, in all other cases, and in the most general case where there is no structural relationship between N and D (for example, when N and D are co-prime, or when N is prime and is greater than D), this method cannot be applied.
Thus, what is needed is an improved method and apparatus for implementing a general convolutional interleaver, with no constraints, in an efficient manner, using (D−1)*(I−1)/2 memory locations for the interleaved data in all cases.